// TestMSmallest.java by Jeff Ward
// This program is a test driver for a program that finds the
// m smallest elements in an array of size n.
// The m elements are returned, in sorted order, in an array of size m.

import java.util.*;

public class TestMSmallest {

	public static void main(String[] args) {
		System.out.println("This program finds the m least elements from a random array of size n.");
		System.out.print("Enter array size (n): ");
		Scanner input = new Scanner(System.in);
		int n = input.nextInt();
		System.out.print("Enter how many values you want from the array (m): ");
		int m = input.nextInt();
		Random rand = new Random(100);
		Integer[] array = new Integer[n];
		for (int i = 0; i < n; i++){
			array[i] = rand.nextInt();
			System.out.println(array[i]);
					
		}
		
		Integer[] smallest = new Integer[m];
		MSmallest.mSmallest(array, smallest);
		System.out.print("Original array of size " + n + ": " );
		System.out.println(Arrays.toString(array));
		System.out.print(m + " least elements: " );
		System.out.println(Arrays.toString(smallest));
		if (checkMSmallest(array, smallest))
			System.out.println("Results are correct ... Good!");
		else {
			System.out.println("Results are incorrect.");
			System.exit(1);
		}
		
		n = 200000;
		int[] mValues = { 20, n};
		for (int mm : mValues) {
			System.out.println("\nNow we'll time it in finding the " + mm
				+ " least elements from an array of size " + n + "...");
			
			Date date = new Date();
			long startTime = date.getTime();
			array = new Integer[n];
			for (int i = 0; i < n; i++)
				array[i] = rand.nextInt();
			smallest = new Integer[mm];
			MSmallest.mSmallest(array, smallest);
			date = new Date();
			long endTime = date.getTime();
			System.out.println("Runtime is " + (endTime - startTime) + " milliseconds.");
			if (checkMSmallest(array, smallest))
				System.out.println("Results are correct ... Good!");
			else {
				System.out.println("Results are incorrect.");
				System.exit(1);
			}
		}
		System.exit(0);
	}
	
	public static <E extends Comparable<? super E>> boolean checkMSmallest(E[] array, E[] smallest) {
		Arrays.sort(array);
		for (int i = 0; i < smallest.length; i++)
			if (smallest[i].compareTo(array[i]) != 0)
				return false;
		return true;		
	}
}